{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Array With Elements Not Equal to Average of Neighbors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: rearrangeArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #构造元素不等于两相邻元素平均值的数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>下标从 0 开始</strong> 的数组 <code>nums</code> ，数组由若干 <strong>互不相同的</strong> 整数组成。你打算重新排列数组中的元素以满足：重排后，数组中的每个元素都 <strong>不等于</strong> 其两侧相邻元素的 <strong>平均值</strong> 。</p>\n",
    "\n",
    "<p>更公式化的说法是，重新排列的数组应当满足这一属性：对于范围&nbsp;<code>1 &lt;= i &lt; nums.length - 1</code> 中的每个 <code>i</code> ，<code>(nums[i-1] + nums[i+1]) / 2</code> <strong>不等于</strong> <code>nums[i]</code> 均成立 。</p>\n",
    "\n",
    "<p>返回满足题意的任一重排结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,2,3,4,5]\n",
    "<strong>输出：</strong>[1,2,4,5,3]\n",
    "<strong>解释：</strong>\n",
    "i=1, nums[i] = 2, 两相邻元素平均值为 (1+4) / 2 = 2.5\n",
    "i=2, nums[i] = 4, 两相邻元素平均值为 (2+5) / 2 = 3.5\n",
    "i=3, nums[i] = 5, 两相邻元素平均值为 (4+3) / 2 = 3.5\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [6,2,0,9,7]\n",
    "<strong>输出：</strong>[9,7,6,2,0]\n",
    "<strong>解释：</strong>\n",
    "i=1, nums[i] = 7, 两相邻元素平均值为 (9+6) / 2 = 7.5\n",
    "i=2, nums[i] = 6, 两相邻元素平均值为 (7+2) / 2 = 4.5\n",
    "i=3, nums[i] = 2, 两相邻元素平均值为 (6+0) / 2 = 3\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [array-with-elements-not-equal-to-average-of-neighbors](https://leetcode.cn/problems/array-with-elements-not-equal-to-average-of-neighbors/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [array-with-elements-not-equal-to-average-of-neighbors](https://leetcode.cn/problems/array-with-elements-not-equal-to-average-of-neighbors/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]', '[6,2,0,9,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        i=1\n",
    "        while i+1<n:\n",
    "            nums[i] ,nums[i+1]=nums[i+1],nums[i]\n",
    "            i+=2\n",
    "        return nums\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        for i in range(0, len(nums)-1, 2):\n",
    "            nums[i], nums[i+1] = nums[i+1], nums[i]\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        i = 1\n",
    "        while i < n - 1:\n",
    "            if nums[i] == (nums[i - 1] + nums[i + 1]) // 2:\n",
    "                random.shuffle(nums)\n",
    "                i = 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return nums\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        \n",
    "        i = 0\n",
    "        while i + 1 < n:\n",
    "            nums[i], nums[i + 1] = nums[i + 1], nums[i]\n",
    "            i += 2\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        # 构造陡峭数组\n",
    "        nums.sort()\n",
    "        for i in range(1, len(nums), 2):\n",
    "            nums[i], nums[i-1] = nums[i-1], nums[i]\n",
    "        return nums\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\r\n",
    "class Solution:\r\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\r\n",
    "        def check(nums: List[int]):\r\n",
    "            for i in range(1, len(nums) - 1):\r\n",
    "                if nums[i] == (nums[i - 1] + nums[i + 1]) / 2:\r\n",
    "                    return False\r\n",
    "\r\n",
    "            return True\r\n",
    "\r\n",
    "        while not check(nums):\r\n",
    "            random.shuffle(nums)\r\n",
    "\r\n",
    "        return nums\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        i = 1\n",
    "        while i<len(nums)-1:\n",
    "            if nums[i]*2 == nums[i-1]+nums[i+1]:\n",
    "                random.shuffle(nums)\n",
    "                i = 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def rearrangeArray(self, nums: list[int]) -> list[int]:\r\n",
    "        nums.sort()\r\n",
    "        n = len(nums)\r\n",
    "        for i in range(1, n - 1, 2):\r\n",
    "            nums[i + 1] , nums[i] = nums[i], nums[i + 1]\r\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        while i < len(nums):\n",
    "            if i + 1 < len(nums):\n",
    "                nums[i],nums[i+1] = nums[i+1], nums[i]\n",
    "\n",
    "                i = i+1\n",
    "            i += 1\n",
    "\n",
    "        return nums\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        left = nums[n//2:]\n",
    "        right = nums[:n//2]\n",
    "        result = [-1]*n\n",
    "        idx = 0 \n",
    "        for i in range(0,n,2):\n",
    "            result[i] = left[idx]\n",
    "            idx += 1\n",
    "        idx = 0\n",
    "        for i in range(1,n,2):\n",
    "            result[i] = right[idx]\n",
    "            idx += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = []\n",
    "        if n & 1:\n",
    "            left,right = nums[:n // 2 + 1],nums[n // 2 + 1:]\n",
    "        else:\n",
    "            left,right = nums[:n // 2],nums[n // 2:]\n",
    "        l,r = 0,len(right) - 1\n",
    "        f = 0\n",
    "        #print(left,right)\n",
    "        while l < len(left) and r >= 0:\n",
    "            if not f:\n",
    "                ans.append(left[l])\n",
    "                l += 1\n",
    "            else:\n",
    "                ans.append(right[r])\n",
    "                r -= 1\n",
    "            f ^= 1\n",
    "        \n",
    "        if l < len(left):\n",
    "            ans.append(left[l])\n",
    "        if r >= 0:\n",
    "            ans.append(right[r])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        # 排序从中间分开 错开一位合并\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = [0] * n\n",
    "        i = 0\n",
    "        for v in nums:\n",
    "            ans[i] = v\n",
    "            i += 2\n",
    "            if i >= n:\n",
    "                i = 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        nums = sorted(nums)\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        i, j = 0, n - 1\n",
    "        while i < j:\n",
    "            ans.append(nums[i])\n",
    "            ans.append(nums[j])\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        if i == j:\n",
    "            ans.append(nums[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        # 构造陡峭数组\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = [0] * n\n",
    "        ans[1::2] = nums[:n >> 1]\n",
    "        ans[::2] = nums[n >> 1:]\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        for a, b in zip(nums[:n//2], nums[-(n//2):]):\n",
    "            ans.append(b)\n",
    "            ans.append(a)\n",
    "        if n % 2:\n",
    "            ans.append(nums[n // 2])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]: \n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        # 计算中位数\n",
    "        k, v = divmod(n,2)\n",
    "        idx = k+v-1\n",
    "        mid = nums[idx] \n",
    "        rv = [0] * n \n",
    "        # 将所有小于等于中位数的数字，放在偶数位上\n",
    "        for i in range(idx+1):\n",
    "            rv[2*i] = nums[i] \n",
    "        # 将其他数字，放在奇数位上\n",
    "        for i in range(idx+1, n):\n",
    "            j = i-(idx+1)\n",
    "            rv[2*j+1] = nums[i]\n",
    "        return rv "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        left = nums[n//2:]\n",
    "        right = nums[:n//2]\n",
    "        result = [-1]*n\n",
    "        idx = 0 \n",
    "        for i in range(0,n,2):\n",
    "            result[i] = left[idx]\n",
    "            idx += 1\n",
    "        idx = 0\n",
    "        for i in range(1,n,2):\n",
    "            result[i] = right[idx]\n",
    "            idx += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = [0] * n\n",
    "        n_larger = 0\n",
    "        n_smaller = 0\n",
    "        mid = n // 2\n",
    "        n_smaller = n // 2\n",
    "        n_larger = n - n_smaller\n",
    "\n",
    "        # put n_larger on even indices\n",
    "        for i in range(n_larger):\n",
    "            res[i * 2] = nums[mid + i]\n",
    "        for i in range(n_smaller):\n",
    "            res[i * 2 + 1] = nums[i]\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "      # 如果重新排列要满足不等于左右两者均值，那么就需要\n",
    "      nums.sort()\n",
    "      i,n = 0, len(nums)\n",
    "      ans = [n] * n\n",
    "      for _,v in enumerate(nums):\n",
    "        ans[i] = v\n",
    "        i += 2\n",
    "        if i >= n:\n",
    "          i = 1\n",
    "      return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        # 将数组排序\n",
    "        nums.sort()\n",
    "        ans = [0]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if i % 2 == 0:\n",
    "                if i+1 < len(ans):\n",
    "                    ans[i+1] = nums[i]\n",
    "                else:\n",
    "                    ans[i]=nums[i]\n",
    "            else:\n",
    "                ans[i-1] = nums[i]\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = [0]*n\n",
    "        i = 0\n",
    "        for num in nums:\n",
    "            if i>= n:\n",
    "                i = 1\n",
    "            ans[i] = num\n",
    "            i += 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        # 把大的数放在两个数中间，把小的数放在两侧\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        lefts = nums[:ceil(n/2)]\n",
    "        rights = nums[ceil(n/2):]\n",
    "        \n",
    "        ans = [0] * n\n",
    "        for i, x in enumerate(lefts):\n",
    "            ans[i*2] = x\n",
    "        for i, x in enumerate(rights):\n",
    "            ans[2*i+1] = x\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        nums = sorted(nums)\n",
    "        i = 0\n",
    "        while (i+1)<len(nums):\n",
    "                temp = nums[i]\n",
    "                nums[i], nums[i+1] = nums[i+1], temp\n",
    "                i+=2\n",
    "        return nums\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = [0] * n\n",
    "        for i in range(0, n, 2):\n",
    "            ans[i] = nums[i//2]\n",
    "        for i in range(1, n, 2):\n",
    "            ans[i] = nums[n - i//2 - 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        sorted_nums = sorted(nums)\n",
    "        res = []\n",
    "        l = 0\n",
    "        r = len(nums) - 1\n",
    "        while l < r:\n",
    "            res.append(sorted_nums[l])\n",
    "            res.append(sorted_nums[r])\n",
    "            l += 1\n",
    "            r -= 1\n",
    "            if l == r:\n",
    "                res.append(sorted_nums[l])\n",
    "                \n",
    "        if res == nums:\n",
    "            res.reverse()\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        # 将数组排序\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        m = (n + 1) // 2\n",
    "        res = []\n",
    "        for i in range(m):\n",
    "            # 放入数值较小的第一部分元素\n",
    "            res.append(nums[i])\n",
    "            if i + m < n:\n",
    "                # （如果有）放入数值较大的第二部分元素\n",
    "                res.append(nums[i + m])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        # 构造陡峭数组\n",
    "        nums.sort()\n",
    "        l = 0\n",
    "        r = len(nums) - 1\n",
    "        ans = []\n",
    "        while l < r:\n",
    "            ans.append(nums[l])\n",
    "            ans.append(nums[r])\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        if l == r:\n",
    "            ans.append(nums[l])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        l = len(nums)\n",
    "        nums.sort()\n",
    "        m = l // 2\n",
    "        new_nums = []\n",
    "        for i in range(l):\n",
    "            if i % 2 == 0:\n",
    "                n = nums[(i//2)]\n",
    "            else:\n",
    "                n = nums[-1-(i//2)]\n",
    "            new_nums.append(n)        \n",
    "        return new_nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        i, j = 0, n - 1\n",
    "        res = []\n",
    "        while i <= j:\n",
    "            if i != j:\n",
    "                res.append(nums[i])\n",
    "                res.append(nums[j])\n",
    "            else:\n",
    "                res.append(nums[i])\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        l, r = 0, len(nums) - 1\n",
    "        ret = []\n",
    "        while l < r:\n",
    "            ret.append(nums[l])\n",
    "            ret.append(nums[r])\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        if l == r:\n",
    "            ret.append(nums[l])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 排序\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        # 将数组排序\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        m = (n + 1) // 2\n",
    "        res = []\n",
    "        for i in range(m):\n",
    "            # 放入数值较小的第一部分元素\n",
    "            res.append(nums[i])\n",
    "            if i + m < n:\n",
    "                # （如果有）放入数值较大的第二部分元素\n",
    "                res.append(nums[i + m])\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        \n",
    "        l, r = 0, len(nums) - 1\n",
    "        while len(res) != len(nums):\n",
    "            res.append(nums[l])\n",
    "            l += 1\n",
    "            if l < r:\n",
    "                res.append(nums[r])\n",
    "                r -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        m = (n + 1) // 2\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            ans.append(nums[i])\n",
    "            if i + m < n:\n",
    "                ans.append(nums[i + m])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rearrangeArray(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = []\n",
    "        l, r = 0, n - 1\n",
    "        while l <= r:\n",
    "            ans.append(nums[l])\n",
    "            if r != l:\n",
    "                ans.append(nums[r])\n",
    "            l += 1\n",
    "            r -= 1\n",
    "\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
